package com.sise.Linked;

/**
 *      234. 回文链表
 *
 *      请判断一个链表是否为回文链表。
 *      输入: 1->2->2->1
 *      输出: true
 */
public class _234_isPalindrome {

    /**
     *  解法一：将头节点保存下来 left，紧接着对链接进行递归到最后一个数字 traverse()，再取出第一个数值 1 与 最后一个数值 1 进行比较，
     *        比较完成之后 left 向后移动一步，head 由于递归也会返回到上一层递归，进而继续比较。
     */

    ListNode left;
    public boolean isPalindrome(ListNode head) {
        left = head;                    // 将左节点保存下来
        return traverse(head);     // 递归到最右边到节点
    }

    private boolean traverse(ListNode head) {
        if (head == null) return true;              // 递归终止条件
        boolean res = traverse(head.next);          // 这里要先进行递归，不能先比较数值，否则 left 赋值会有问题
        res = res && (head.val == left.val);        // 如果数值相等，同时以往的递归为 true，那就说明当前还是 true
        left = left.next;                           // 将左节点向右移动一位
        return res;
    }

    /**
     *  解法二：使用快慢指针，当快指针到达终点的时候，慢指针恰好在中间，同时慢指针将前半部分反转链表，最后再进行比较
     */
    public boolean isPalindrome_2(ListNode head) {
        if (head == null || head.next == null){
            return true;
        }

        ListNode slow = head;
        ListNode fast = head;
        ListNode pre = head;
        ListNode prepre = null;

        while (fast != null && fast.next != null){
            pre = slow;                 // 将慢指针赋值给 pre
            slow = slow.next;
            fast = fast.next.next;
            pre.next = prepre;          // 反转链表， prepre <- pre
            prepre = pre;               // 将 prepre 往前挪一步
        }

        // 由于 fast 每次都是走两步的，故此有两种可能，一种是指向 null，一种是 指向最后一个节点，如果指向最后一个节点的话，说明链表个数为 奇数，
        // 就让慢指针往后移动一步到中心位置。例如[1,2,3,2,1], 当 fast = 5 时， slow = 3，当这时候的 3 是没有意义的，故此将 slow 往前移动一步
        // 如果 fast 为 null，例如 [1,2,2,1]，那么 slow 就不用移动了
        if (fast != null){
            slow = slow.next;
        }

        while (pre != null && slow != null){
            if (pre.val != slow.val){
                return false;
            }
            pre = pre.next;
            slow = slow.next;
        }
        return true;
    }
}
